import java.util.ArrayList;
import java.util.List;

public class BF {
    /**
     * 判断主串中是否含有子串
     * @param str 主串
     * @param target 子串
     * @return 主串中含有子串，返回主串中子串第一次出现的起始下标；若不含有，返回 -1
     */
    public int BF1(String str, String target) {
        // 处理特殊情况
        if (str == null || target == null) {
            return -1;
        }
        int strLen = str.length();
        int targetLen = target.length();
        if (strLen == 0 || strLen < targetLen) {
            return -1;
        }
        // 开始判断
        int i = 0, j = 0;
        while (i < strLen && j < targetLen) {
            // 判断 str 中 i 位置字符是否与 target 中j 位置字符相同
            if (str.charAt(i) == target.charAt(j)) {
                // 相同，i 和 j 都向后移动
                i++;
                j++;
            } else {
                // 不相同，i 和 j 都进行回退
                i = i - j + 1;
                j = 0;
            }
        }
        // 子串先遍历完
        if (j >= targetLen) {
            return i - j;
        } else {
            // 主串先遍历完
            return -1;
        }
    }
    /**
     * 查找主串中与子串相同的字符串的所有起始位置
     * @param str 主串
     * @param target 子串
     * @return 查询结果集
     */
    public List<Integer> BF(String str, String target) {
        List<Integer> ret = new ArrayList<>();
        // 处理特殊情况
        if (str == null || target == null) {
            return ret;
        }
        int strLen = str.length();
        int targetLen = target.length();
        if (strLen == 0 || strLen < targetLen) {
            return ret;
        }
        // 开始判断
        int i = 0, j = 0;
        while (i < strLen) {
            // 判断 str 中 i 位置字符是否与 target 中j 位置字符相同
            if (str.charAt(i) == target.charAt(j)) {
                // 相同，i 和 j 都向后移动
                i++;
                j++;
            } else {
                // 不相同，i 和 j 都进行回退
                i = i - j + 1;
                j = 0;
            }
            // 判断子串是否遍历完成
            if (j >= targetLen) {
                ret.add(i - j);
                i = i - j + 1;
                j = 0;
            }
        }
        return ret;
    }


    public static void main(String[] args) {
        BF bf = new BF();
        System.out.println(bf.BF("aaaaaa", "ab"));
    }
}
